//题目:
// 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
// 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

// 示例 1：
// 输入：n = 12
// 输出：3 
// 解释：12 = 4 + 4 + 4

// 示例 2：
// 输入：n = 13
// 输出：2
// 解释：13 = 4 + 9
#include<iostream>
#include<limits.h>
#include<vector>

using namespace std;
//代码
class Solution 
{
    
public:
    int numSquares(int sum) 
    {
        //一.先找出[1,10000]中所有的完全平方数，并将其存到nums中
        vector<int> nums;
        for(int i=1;i*i<=10000;i++)
            nums.push_back(i*i);
        //二.动态规划
        // //1.创建dp表————dp[i][j]表示：选到第i个数、和为j时，完全平方数的最少数量
        // int n=nums.size();
        // vector<vector<int>> dp(n+1,vector<int>(sum+1,0x3fffffff));
        // //2.初始化
        // dp[0][0]=0;
        // //3.填表————动态转移方程：dp[i][j]=min(dp[i-1][j],dp[i][j-nums[i]]+1)
        // for(int i=1;i<=n;i++)
        // {
        //     for(int j=0;j<=sum;j++)
        //     {
        //         //暴力遍历————超时
        //         // for(int k=0;k*nums[i-1]<=j;k++)
        //         //     dp[i][j]=min(dp[i][j],dp[i-1][j-k*nums[i-1]]+k);

        //         dp[i][j]=dp[i-1][j];
        //         if(j-nums[i-1]>=0)
        //             dp[i][j]=min(dp[i-1][j],dp[i][j-nums[i-1]]+1);
        //     }
        // }
        // //4.确定返回值
        // return dp[n][sum];

        //动态规划————空间优化
        //1.创建dp表————dp[i][j]表示：选到第i个数、和为j时，完全平方数的最少数量
        int n=nums.size();
        vector<int> dp(sum+1,0x3fffffff);
        //2.初始化
        dp[0]=0;
        //3.填表————动态转移方程：dp[i][j]=min(dp[i-1][j],dp[i][j-nums[i]]+1)
        for(int i=1;i<=n;i++)
        {
            for(int j=nums[i-1];j<=sum;j++)
            {
                //暴力遍历————超时
                // for(int k=0;k*nums[i-1]<=j;k++)
                //     dp[i][j]=min(dp[i][j],dp[i-1][j-k*nums[i-1]]+k);

                dp[j]=min(dp[j],dp[j-nums[i-1]]+1);
            }
        }
        //4.确定返回值
        return dp[sum];
    }
};